package com.leetcode.linkedList;

import com.leetcode.basic.ListNode;

/**
 * @author Dennis Li
 * @date 2020/6/13 22:58
 */
public class SplitListToParts_725 {

    public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] nodes = new ListNode[k];
        if (root == null) return nodes;
        ListNode cur = root, tale, head;
        int len = 0;
        while (cur != null) {
            cur = cur.next;
            len++;
        }
        cur = root;
        // 关键在于通过余数和商同时来确定链表的长度
        int mod = len % k, num = len / k, index = 0;
        // 修改链表
        /**
         * 1.固化头结点
         * 2.中间修改
         * 3.尾结点截断 -- 注意用一个中介结点记录
         */
        while (cur != null) {
            head = cur;
            // 这一段是精髓
            int count = mod-- > 0 ? num + 1 : num;
            while (--count > 0) {
                cur = cur.next;
            }
            tale = cur;
            cur = cur.next;
            // 注意链表切断
            tale.next = null;
            nodes[index++] = head;
        }
        return nodes;
    }


}
